You have to place several advertisements for your company in a TV channel on
a specific day. The possible time slots for the advertisements are $t_1, t_2, . . . , t_n$;
each slot $t_i$ has its own expected revenue $r_i$. You have to choose the time slots
in order to maximize the total expected revenue (which is the sum of revenues
of the time slots chosen) with the restriction that no two advertisements must be
occur within $T$ time units of each other.

Design a dynamic programming solution for this problem. Does a greedy strategy
return an optimal solution? (Define your choice of greedy; then either prove
that it is optimal or give a counterexample.)

\vspace{10pt}
First, let's remark that in our solution the time spot sequence will be considered to be in increasing order.

Our dynamic programming solution will use the following idea:

Suppose we know all optimal solutions for subproblems $P_1,\dots, P_k$ where for each $i \le k$ the subproblem $P_i$ contains only the time spots up to $t_i$.

Then the solution for the subproblem $P_{k+1}$, where all time spots up to $t_{k+1}$, can follow two options: we place the advertisement to the new time spot $t_{k+1}$ or we don't.

Let's consider the case when we place the advertisement to $t_{k+1}$. Because of this placement and the problem restrictions, we cannot now use any time spot within $T$ time units of $t_{k+1}$. So the result solution will use in addition to $t_{k+1}$ only the time spots remaining after removing forbidden ones, that is it will use the time spots $t_i$ that satisfy the inequation $t_i < t_{k+1} - T$ (as the timespot sequence is considered to be in increasing order). Because of order we can define the maximal index $i$ of $t_i$ satisfying this inequation, then all time spots before this index including it are guaranteed to satisfy the inequation and all time spots after it don't satisfy it. Let's denote this found index as $i_{max}(k + 1)$. So the best solution in this case would be to use the best solution on the subproblem $P_{i_{max}(k + 1)}$ and add our timespot $t_{k+1}$ to it.

In the second case, when the time spot $t_{k+1}$ is not used, we can use all other timespots before it in solution. So the best one will be the same as the best solution on subproblem $P_k$, where all time spots up to $t_k$ are given.

Among those two cases best solution we'll choose the best one which will be the best solution on the subproblem $P_{k+1}$, as we considered all possible variants and in each of them found the best solution.

\vspace{5pt}
Other consideration is how to reconstruct the actual choice of time spots though this algorithm. To backtrack we'll start from the found optimal solution of the problem $P_n$ stored in $P$[$n$]. Then we'll check by what variant (choosing last time spot $t_n$ or not) it was obtained: to do so we'll just check which of two possible variants discussed before $P$[$n$] is equal to. If it was obtained though choosing $t_n$, then $t_n$ is added to the set of chosen spots $S$ and we go to check the next first possible time spot to add: $t_{i_{max}(n)}$ (as we cannot add any time spots between those two). If not ($P$[$n$] was found not choosing $t_n$), that is if $P$[$n$]=$P$[$n-1$], then we'll not add $t_n$ to set of chosen spots and will just go to the next possible to add spot $t_{n-1}$. By the same logic we'll continue to go back through the array $P$ till the beginning of it.

\newpage
The sketch of our dynamic programming algorithm to get the result revenue:

\begin{figure}[h]
\lstset{language=C, tabsize=2, frame=none, numbers=left, basicstyle=\small}
	\begin{lstlisting}[language=C]
	Given: sorted timespot set TS[1..n], revenue set R[1..n], time constraint T	
	Create an array P[1..n]
	P[1] = R[1]
	for (int k = 1; k < n; k++)
		int maxindex = k;
		while ((TS[maxindex] >= TS[k+1] - T) and (maxindex > 0))
			maxindex--;
		if (maxindex == 0)
			P[k+1] = max(P[k], R[k+1]);
		else
 			P[k+1] = max(P[k], R[k+1] + P[maxindex]);
	return P[n];
	\end{lstlisting}
\end{figure}

\vspace{5pt}
The sketch of backtracking part of the algorithm to get the set of chosen time spots:

\begin{figure}[h]
\lstset{language=C, tabsize=2, frame=none, numbers=left, basicstyle=\small}
	\begin{lstlisting}[language=C]
	Given: sorted timespot set TS[1..n], optimal solutions of subproblems P (result of previous algorithm)	
	S = empty
	k = n
	consider P[0] = 0
	while (k > 0) {
		int maxindex = k - 1;
		while ((TS[maxindex] >= TS[k] - T) and (maxindex > 0))
			maxindex--;
		
		if (P[k] == R[k] + P[maxindex])
			k = maxindex;
		else
			k--;
	}
	\end{lstlisting}
\end{figure}


The time complexity of dynamic programming of finding optimal revenue and array \textit{P} construction is $O(nT)$ in assumption that the distance between two spots cannot be less than one time unit, as in this case for each of the time spots we at most go $T$ steps back to find the maximum index of remaining possibly used time spots. Let's remark, that without this assumption this part in worst-case will work $O(n^2)$, as the number of steps back cannot exceed $n$ for each new time spot. Time complexity of backtracking is $O(n)$, because we only going step by step back without return. Here we need to state, that as the algorithm require the presorted list of time spots, it would take extra $O(n \log n)$ to sort it. So with the assumption that the distance between two spots cannot be less than one time unit, the overall time complexity is $O(n \log n)$. Without this assumption the overall complexity is $O(n^2)$.

\newpage
Now let's consider the following greedy strategy:

\vspace{10pt}
First, set $S=\emptyset$ will contain the chosen time spots and set $U=TS$ will contain remaining spots possible to choose. Then the algorithm is

while $U != \emptyset$ do

\hspace{15pt}find $t\in U$ with maximum revenue

\hspace{15pt}put found $t$ to $S$

\hspace{15pt}delete $t$ from $U$

\hspace{15pt}delete from $U$ all time spots that are within $T$ time units from $t$ 

\vspace{10pt}
The result set $S$ will be returned by the algorithm.

This greedy algorithm doesn't always return the optimal solution. We'll provide the following counterexample: Suppose we have 3 time spots $t_1 = 1$, $t_2 = 2$, $t_3 = 3$, that have revenues $r_1 = 7$, $r_2 = 8$, $r_3 = 7$. The parameter $T$ is set to $1$. In this case it's clear that optimal solution would be to choose $t_1$ and $t_3$ time spots, resulting in $r_1 + r_3 = 14$ revenue. But our greedy algorithm would first choose $t_2$ as the time spot with largest revenue, as then it cannot choose anything else. So the result of greedy algorithm is $8$ which is clearly less than optimal.

